{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #字符串的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #hash-table #two-pointers #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #哈希表 #双指针 #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkInclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串的排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两个字符串&nbsp;<code>s1</code>&nbsp;和&nbsp;<code>s2</code>，写一个函数来判断 <code>s2</code> 是否包含 <code>s1</code><strong>&nbsp;</strong>的某个变位词。</p>\n",
    "\n",
    "<p>换句话说，第一个字符串的排列之一是第二个字符串的 <strong>子串</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s1 = &quot;ab&quot; s2 = &quot;eidbaooo&quot;\n",
    "<strong>输出: </strong>True\n",
    "<strong>解释:</strong> s2 包含 s1 的排列之一 (&quot;ba&quot;).\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>s1= &quot;ab&quot; s2 = &quot;eidboaoo&quot;\n",
    "<strong>输出:</strong> False\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s1.length, s2.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s1</code> 和 <code>s2</code> 仅包含小写字母</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 567&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/permutation-in-string/\">https://leetcode-cn.com/problems/permutation-in-string/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [MPnaiL](https://leetcode.cn/problems/MPnaiL/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [MPnaiL](https://leetcode.cn/problems/MPnaiL/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"ab\"\\n\"eidbaooo\"', '\"ab\"\\n\"eidboaoo\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        ref = {item: 0 for item in s2}\n",
    "        count = {item: 0 for item in s2}\n",
    "        for si in s1:\n",
    "            if si not in s2:\n",
    "                return False\n",
    "            else:\n",
    "                ref[si] += 1\n",
    "        n = len(s1)\n",
    "        for i in range(len(s2)):\n",
    "            if i < n:\n",
    "                count[s2[i]] += 1\n",
    "            else:\n",
    "                count[s2[i]] += 1\n",
    "                count[s2[i - n]] -= 1\n",
    "            if count == ref:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        cnt = Counter(s1)\n",
    "        num = len(s1)\n",
    "        n = len(s2)\n",
    "        idx = defaultdict(list)\n",
    "        i = 0\n",
    "        tmp = Counter(s1)\n",
    "        while i < n:\n",
    "            if s2[i] not in tmp or tmp[s2[i]] == 0:\n",
    "                #print(i, tmp, idx)\n",
    "                tmp = Counter(s1)\n",
    "                num = len(s1)\n",
    "                if s2[i] in idx:\n",
    "                    i = idx[s2[i]][0] + 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                idx = defaultdict(list)\n",
    "            else:\n",
    "                tmp[s2[i]] -= 1\n",
    "                num -= 1\n",
    "                idx[s2[i]].append(i)\n",
    "                if num == 0:\n",
    "                    return True\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "import copy\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        s1Length=len(s1)\n",
    "        s2Length=len(s2)\n",
    "        s1DictFixed=defaultdict(int)\n",
    "        s1Dict=defaultdict(int)\n",
    "        s1NumSumFixed=0\n",
    "        s1NumSum=0\n",
    "        s2Dict=defaultdict(list)\n",
    "        leftPointer=0\n",
    "        rightPointer=0\n",
    "        ans=False\n",
    "        for i in s1:\n",
    "            s1DictFixed[i]+=1\n",
    "            s1Dict[i]+=1\n",
    "            s1NumSumFixed+=1\n",
    "            s1NumSum+=1\n",
    "        \n",
    "        while rightPointer<s2Length:\n",
    "            if s1Dict[s2[rightPointer]]>0:\n",
    "                s1Dict[s2[rightPointer]]-=1\n",
    "                s1NumSum-=1\n",
    "                s2Dict[s2[rightPointer]].append(rightPointer)\n",
    "                rightPointer+=1\n",
    "                if s1NumSum==0:\n",
    "                    ans=True\n",
    "                \n",
    "            elif s1Dict[s2[rightPointer]]==0:\n",
    "                if s2[rightPointer] in s2Dict:\n",
    "                    leftPointer=s2Dict[s2[rightPointer]][0]+1\n",
    "                    s2Dict[s2[rightPointer]].pop()\n",
    "                elif s2[rightPointer] not in s2Dict:\n",
    "                    leftPointer=rightPointer+1\n",
    "                rightPointer=leftPointer\n",
    "                s1Dict=copy.deepcopy(s1DictFixed)\n",
    "                s1NumSum=s1NumSumFixed\n",
    "                s2Dict=defaultdict(list)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m,n = len(s1),len(s2)\n",
    "        if m>n:\n",
    "            return False\n",
    "        cnt = Counter(s1)\n",
    "        need = m\n",
    "        for right in range(n):\n",
    "            ch = s2[right]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch] > 0:\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            left = right - m\n",
    "            if left >= 0:\n",
    "                ch = s2[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch] >= 0:\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "            if need == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        anum,bnum = [0]*26,[0]*26\n",
    "        if len(s1)>len(s2):\n",
    "            return False\n",
    "        for i in range(len(s1)):\n",
    "            anum[ord(s1[i])-ord('a')]+=1\n",
    "            bnum[ord(s2[i])-ord('a')]+=1\n",
    "        \n",
    "        for j in range(len(s1),len(s2)):\n",
    "            if anum==bnum:\n",
    "                return True\n",
    "            bnum[ord(s2[j-len(s1)])-ord('a')]-=1\n",
    "            bnum[ord(s2[j])-ord('a')]+=1\n",
    "        \n",
    "        return anum==bnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n, m = len(s1), len(s2)\n",
    "        arr1, arr2 = [0] * 26, [0] * 26\n",
    "        if n > m: return False\n",
    "        for i in range(n):\n",
    "            arr1[ord(s1[i]) - ord('a')] += 1\n",
    "            arr2[ord(s2[i]) - ord('a')] += 1\n",
    "        for j in range(n, m):\n",
    "            if arr1 == arr2: return True\n",
    "            arr2[ord(s2[j - n]) - ord('a')] -= 1\n",
    "            arr2[ord(s2[j]) - ord('a')] += 1\n",
    "        return arr1 == arr2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        cnt1 = Counter(s1)\n",
    "        cnt2 = Counter(s2[:n1 - 1])\n",
    "        i, j = 0, n1 - 1\n",
    "        while j < n2:\n",
    "            cnt2[s2[j]] += 1\n",
    "            if cnt1 == cnt2:\n",
    "                return True\n",
    "            \n",
    "            cnt2[s2[i]] -= 1\n",
    "\n",
    "            i += 1\n",
    "            j += 1\n",
    "            \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "        if n2 < n1: return False\n",
    "        memo1 = [0 for _ in range(26)]\n",
    "        for i in range(n1):\n",
    "            memo1[ord(s1[i])-ord(\"a\")] += 1\n",
    "        \n",
    "        left, right = 0, n1-1\n",
    "        memo2 = [0 for _ in range(26)]\n",
    "        for i in range(left,right+1):\n",
    "            memo2[ord(s2[i])-ord(\"a\")] += 1\n",
    "        while right <= n2-1:\n",
    "            if memo2 == memo1:\n",
    "                return True\n",
    "            else:\n",
    "                if right == n2-1:\n",
    "                    return False\n",
    "                else:\n",
    "                    memo2[ord(s2[left])-ord(\"a\")] -= 1\n",
    "                    left += 1\n",
    "                    right += 1\n",
    "                    memo2[ord(s2[right])-ord(\"a\")] += 1\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        arr1, arr2, lg = [0] * 26, [0] * 26, len(s1)\n",
    "        if lg > len(s2):\n",
    "            return False\n",
    "\n",
    "        for i in range(lg):\n",
    "            arr1[ord(s1[i]) - ord('a')] += 1\n",
    "            arr2[ord(s2[i]) - ord('a')] += 1\n",
    "\n",
    "        for j in range(lg, len(s2)):\n",
    "            if arr1 == arr2:\n",
    "                return True\n",
    "            arr2[ord(s2[j - lg]) - ord('a')] -= 1\n",
    "            arr2[ord(s2[j]) - ord('a')] += 1\n",
    "        return arr1 == arr2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        arr1, arr2 = [0] * 26, [0] * 26\n",
    "        n, m = len(s1), len(s2)\n",
    "        for s in s1: \n",
    "            arr1[ord(s) - ord('a')] += 1\n",
    "        for i in range(m):\n",
    "            arr2[ord(s2[i]) - ord('a')] += 1\n",
    "            if i >= n-1:\n",
    "                if arr1 == arr2:\n",
    "                    return True\n",
    "                arr2[ord(s2[i-n+1]) - ord('a')] -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        s1_count = [0] * 26\n",
    "        s2_count = [0] * 26\n",
    "\n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "\n",
    "        for char in s1:\n",
    "            s1_count[ord(char) - ord('a')] += 1\n",
    "\n",
    "        for i in range(len(s1)):\n",
    "            s2_count[ord(s2[i]) - ord('a')] += 1\n",
    "\n",
    "        if s1_count == s2_count:\n",
    "            return True\n",
    "\n",
    "        for i in range(1, len(s2) - len(s1) + 1):\n",
    "            s2_count[ord(s2[i - 1]) - ord('a')] -= 1\n",
    "            s2_count[ord(s2[i + len(s1) - 1]) - ord('a')] += 1\n",
    "\n",
    "            if s1_count == s2_count:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        s1count = {item: 0 for item in s2}\n",
    "        count = {item: 0 for item in s2}\n",
    "        for s in s1:\n",
    "            if s not in s2:\n",
    "                return False\n",
    "            else:\n",
    "                s1count[s] += 1\n",
    "        for i in range(len(s2)):\n",
    "            if i < n: count[s2[i]] += 1\n",
    "            else:\n",
    "                count[s2[i]] += 1\n",
    "                count[s2[i-n]] -= 1\n",
    "            if count == s1count: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n, m = len(s1), len(s2)\n",
    "        cnt1 = [0] * 26\n",
    "        cnt2 = [0] * 26\n",
    "        for s in s1:\n",
    "            cnt1[ord(s) - ord('a')] += 1\n",
    "        for s in s2:\n",
    "            cnt2[ord(s) - ord('a')] += 1\n",
    "        if n > m:\n",
    "            return False\n",
    "\n",
    "        for i in range(0, m-n+1):\n",
    "            cnt2 = [0] * 26\n",
    "            j = i + n\n",
    "            for s in s2[i:j]:\n",
    "                cnt2[ord(s) - ord('a')] += 1\n",
    "            if  cnt1 == cnt2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        dic1,dic2=Counter(s1),Counter()\n",
    "        # dic1,dic2={},{}\n",
    "        # for c in s1:\n",
    "        #     dic1[c]=dic1.get(c,0)+1\n",
    "        l,r=0,0\n",
    "        val=0\n",
    "        while r< len(s2):\n",
    "            if s2[r] in dic1:\n",
    "                dic2[s2[r]]+=1\n",
    "                # dic2[s2[r]]=dic2.get(s2[r],0)+1\n",
    "            \n",
    "            if s2[r] in dic1 and dic1[s2[r]]==dic2[s2[r]]:\n",
    "                val+=1\n",
    "            while r-l+1>= len(s1):\n",
    "                if val==len(dic1):return True\n",
    "                if s2[l] in dic1 and dic1[s2[l]]==dic2[s2[l]]:\n",
    "                    \n",
    "                    val-=1\n",
    "                dic2[s2[l]]-=1\n",
    "                l+=1\n",
    "            \n",
    "            \n",
    "            r+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n, m = len(s1), len(s2)\n",
    "        l, r = 0, n\n",
    "        arr = [0] * 26\n",
    "        for c in s1:\n",
    "            arr[(ord(c) - ord('a'))] += 1\n",
    "        while r <= m:\n",
    "            tmp = [0] * 26\n",
    "            for i in range(l, r):\n",
    "                tmp[(ord(s2[i]) - ord('a'))] += 1\n",
    "            if arr == tmp: return True\n",
    "            l += 1\n",
    "            r += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        c1 = collections.Counter(s1)\n",
    "        c2 = collections.Counter(s2[:len(s1)])\n",
    "        if c2 - c1 == collections.Counter() and c1-c2 == collections.Counter():\n",
    "            return True\n",
    "\n",
    "        for i in range(1, len(s2)-len(s1)+1):\n",
    "            c2[s2[i-1]] -= 1\n",
    "            c2[s2[i+len(s1)-1]] += 1\n",
    "            if c2 - c1 == collections.Counter() and c1-c2 == collections.Counter():\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m=len(s1)\n",
    "        n=len(s2)\n",
    "\n",
    "        if m>n:\n",
    "            return False\n",
    "        \n",
    "        cnt=collections.Counter(s1)\n",
    "        need=m\n",
    "\n",
    "        for right in range(n):\n",
    "            #窗口右边界\n",
    "            ch=s2[right]\n",
    "            if ch in cnt:\n",
    "                if cnt[ch]>0:\n",
    "                    need-=1\n",
    "                cnt[ch]-=1\n",
    "            #窗口右边界\n",
    "            left=right-m\n",
    "            if left>=0:\n",
    "                ch=s2[left]\n",
    "                if ch in cnt:\n",
    "                    if cnt[ch]>=0:\n",
    "                        need+=1\n",
    "                    cnt[ch]+=1\n",
    "            \n",
    "            if need==0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    res = []\n",
    "    path = \"\"\n",
    "    def backtrack(self,str_s,k,used):\n",
    "        if len(self.path) == k:\n",
    "            # print(len(self.path),self.path)\n",
    "            self.res.append(self.path)\n",
    "            return 0 \n",
    "        #\n",
    "        for i in range(len(str_s)):\n",
    "            # print(self.path,'-',used)\n",
    "            if used[i]==0:\n",
    "                self.path+=(str_s[i])\n",
    "                used[i] =1\n",
    "                self.backtrack(str_s,k,used)\n",
    "                used[i] = 0\n",
    "                self.path= self.path[:-1]\n",
    "            else:\n",
    "                continue\n",
    "    \n",
    "\n",
    "\n",
    "\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m > n:\n",
    "            return False\n",
    "        \n",
    "        cnt = collections.Counter(s1)   # 哈希表：记录需要匹配到的各个字符的数目\n",
    "        need = m                        # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        for right in range(n):\n",
    "            \n",
    "            # 窗口右边界\n",
    "            ch = s2[right]              # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符ch位于s1中\n",
    "                if cnt[ch] > 0:         # 此时新加入窗口中的字符ch对need有影响\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            # 窗口左边界\n",
    "            left = right - m\n",
    "            if left >= 0:\n",
    "                ch = s2[left]\n",
    "                if ch in cnt:           # 刚滑出的字符位于s1中\n",
    "                    if cnt[ch] >= 0:    # 此时滑出窗口的字符ch对need有影响\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "\n",
    "            if need == 0:               # 找到了一个满足题意的窗口\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        s1_length = len(s1)\n",
    "        s2_length = len(s2)\n",
    "        if s1_length > s2_length: return False\n",
    "        need = defaultdict(int)\n",
    "        window = defaultdict(int)\n",
    "        for c in s1:\n",
    "            need[c] += 1\n",
    "        l, r = 0, 0\n",
    "        valid = 0\n",
    "        while r < s2_length:\n",
    "            c = s2[r]\n",
    "            r += 1\n",
    "            if c in need:\n",
    "                window[c] += 1\n",
    "                if window[c] == need[c]:\n",
    "                    valid += 1\n",
    "            while r - l >= s1_length:\n",
    "                c = s2[l]\n",
    "                l += 1\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "                if c in need:\n",
    "                    if window[c] == need[c]:\n",
    "                        valid -= 1\n",
    "                    window[c] -= 1\n",
    "                \n",
    "                # print(l, r, window)\n",
    "                    \n",
    "                \n",
    "        \n",
    "        return False\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1),len(s2)\n",
    "\n",
    "        cnt = collections.Counter(s1)\n",
    "        need = m\n",
    "        for right in range(n):\n",
    "            ch = s2[right]\n",
    "            if ch in cnt :\n",
    "                if cnt[ch] > 0 :\n",
    "                    need -= 1\n",
    "                cnt[ch] -= 1\n",
    "            \n",
    "            left = right - m \n",
    "            if left >= 0 :\n",
    "                ch = s2[left]\n",
    "                if ch in cnt :\n",
    "                    if cnt[ch] >= 0 :\n",
    "                        need += 1\n",
    "                    cnt[ch] += 1\n",
    "\n",
    "            if need == 0:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        if m > n:\n",
    "            return False\n",
    "        \n",
    "        mem = defaultdict(int)\n",
    "\n",
    "        for i in range(m):\n",
    "            mem[s1[i]] += 1\n",
    "\n",
    "        for i in range(m):\n",
    "            mem[s2[i]] -= 1\n",
    "\n",
    "        slow, fast = 0, m\n",
    "\n",
    "        while fast < n:\n",
    "            if sum([abs(_) for _ in mem.values()]) == 0:\n",
    "                return True\n",
    "            \n",
    "            mem[s2[slow]] += 1\n",
    "            mem[s2[fast]] -= 1\n",
    "            slow += 1\n",
    "            fast += 1\n",
    "        \n",
    "        if sum([abs(_) for _ in mem.values()]) == 0:\n",
    "            return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        # 字符串、哈希表、滑动窗口\n",
    "        # 本题和438题思路完全一样，window定宽\n",
    "        from collections import Counter\n",
    "        need = Counter(s1)\n",
    "        left, right = 0, len(s1) - 1\n",
    "        while right < len(s2):\n",
    "            window = Counter(s2[left: right + 1])\n",
    "            if need == window:\n",
    "                return True\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        anum,bnum = [0]*26,[0]*26\n",
    "        if len(s1)>len(s2):\n",
    "            return False\n",
    "        for i in range(len(s1)):\n",
    "            anum[ord(s1[i])-ord('a')]+=1\n",
    "            bnum[ord(s2[i])-ord('a')]+=1\n",
    "        \n",
    "        for i in range(len(s1),len(s2)):\n",
    "            if anum==bnum:\n",
    "                return True\n",
    "            bnum[ord(s2[i])-ord('a')]+=1\n",
    "            bnum[ord(s2[i-len(s1)])-ord('a')]-=1\n",
    "        return anum==bnum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        \n",
    "        len_1, len_2 = len(s1), len(s2)\n",
    "        if len_1 > len_2: return False\n",
    "\n",
    "        map_s1 = Counter(s1)\n",
    "\n",
    "        for i in range(len_1): # 初始化窗口\n",
    "            if s2[i] in map_s1:\n",
    "                map_s1[s2[i]] -= 1\n",
    "            if max(list(map_s1.values())) == 0:\n",
    "                return True\n",
    "        \n",
    "        for p in range(len_1, len_2): # 滑窗\n",
    "            if s2[p] in map_s1:\n",
    "                map_s1[s2[p]] -= 1\n",
    "            if s2[p-len_1] in map_s1:\n",
    "                map_s1[s2[p-len_1]] += 1\n",
    "            if max(list(map_s1.values())) == 0:\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "# \"adc\"\\n\"dcda\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        need = Counter(s1)\n",
    "        left, right = 0, len(s1) - 1\n",
    "        while right < len(s2):\n",
    "            window = Counter(s2[left: right + 1])\n",
    "            if need == window:\n",
    "                return True\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "\n",
    "        cnt1 = Counter(s1)\n",
    "        cnt2 = Counter()\n",
    "\n",
    "        l = 0\n",
    "        for r in range(len(s2)):\n",
    "            cnt2[s2[r]] += 1\n",
    "\n",
    "            if r - l + 1 == len(s1):\n",
    "                if cnt1 == cnt2:\n",
    "                    return True\n",
    "\n",
    "                cnt2[s2[l]] -= 1\n",
    "                if cnt2[s2[l]] == 0:\n",
    "                    cnt2.pop(s2[l])\n",
    "                l += 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        # 数组、滑动窗口\n",
    "        from collections import Counter\n",
    "        need = Counter(s1)\n",
    "        left, right = 0, len(s1) - 1\n",
    "        while right < len(s2):\n",
    "            window = Counter(s2[left: right + 1])\n",
    "            if need == window:\n",
    "                return True\n",
    "            left += 1\n",
    "            right += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n, m = len(s1), len(s2)\n",
    "        cnt1 = [0] * 26\n",
    "        cnt2 = [0] * 26\n",
    "        for s in s1:\n",
    "            cnt1[ord(s) - ord('a')] += 1\n",
    "        if n > m:\n",
    "            return False\n",
    "\n",
    "        for i in range(0, m-n+1):\n",
    "            cnt2 = [0] * 26\n",
    "            j = i + n\n",
    "            for s in s2[i:j]:\n",
    "                cnt2[ord(s) - ord('a')] += 1\n",
    "            if  cnt1 == cnt2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        arr1, arr2, lg = [0] * 26, [0] * 26, len(s1)\n",
    "        if lg > len(s2):\n",
    "            return False\n",
    "        for i in range(lg):\n",
    "            arr1[ord(s1[i]) - ord('a')] += 1\n",
    "            arr2[ord(s2[i]) - ord('a')] += 1\n",
    "        for j in range(lg, len(s2)):\n",
    "            if arr1 == arr2:\n",
    "                return True\n",
    "            arr2[ord(s2[j - lg]) - ord('a')] -= 1\n",
    "            arr2[ord(s2[j]) - ord('a')] += 1\n",
    "        return arr1 == arr2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        # 计算 s1 的字符频率\n",
    "        s1_counter = Counter(s1)\n",
    "        \n",
    "        # 初始化 s2 窗口的字符频率\n",
    "        s2_counter = Counter()\n",
    "        \n",
    "        # 初始化窗口的左右边界\n",
    "        left, right = 0, 0\n",
    "        \n",
    "        while right < len(s2):\n",
    "            # 扩大窗口的右边界\n",
    "            s2_counter[s2[right]] += 1\n",
    "            right += 1\n",
    "            \n",
    "            # 如果窗口大小大于 s1 的长度，缩小窗口的左边界\n",
    "            if right - left > len(s1):\n",
    "                if s2_counter[s2[left]] == 1:\n",
    "                    del s2_counter[s2[left]]\n",
    "                else:\n",
    "                    s2_counter[s2[left]] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            # 检查窗口内的字符频率是否与 s1 匹配\n",
    "            if s1_counter == s2_counter:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        s1Map  = {}\n",
    "        n, m = len(s1), len(s2)\n",
    "        for s in s1: \n",
    "            s1Map[s] = s1Map.get(s, 0) + 1\n",
    "        s2Map = {}\n",
    "        for i in range(m):\n",
    "            s2Map[s2[i]] = s2Map.get(s2[i], 0) + 1\n",
    "            if i >= n-1:\n",
    "                if s1Map == s2Map:\n",
    "                    return True\n",
    "                s2Map[s2[i-n+1]] = s2Map[s2[i-n+1]] - 1\n",
    "                if s2Map[s2[i-n+1]] == 0:\n",
    "                    del s2Map[s2[i-n+1]]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1) - 1, len(s2)\n",
    "        c1, c2 = Counter(s1), Counter(s2[: n1])\n",
    "        for i in range(n2 - n1):\n",
    "            c2[s2[i + n1]] += 1\n",
    "            if c1 == c2: return True\n",
    "            c2[s2[i]] -= 1 \n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        record = {}\n",
    "        for c in s1:\n",
    "            record[c] = record.get(c, 0)+1\n",
    "        distance = len(record)\n",
    "        move = {}\n",
    "        left = 0\n",
    "        for i in range(len(s2)):\n",
    "            if i>=len(s1):\n",
    "                if s2[i-len(s1)] in record:\n",
    "                    move[s2[i-len(s1)]] -= 1\n",
    "                    if move[s2[i-len(s1)]]+1 == record[s2[i-len(s1)]]:\n",
    "                        distance += 1\n",
    "            if s2[i] in record:\n",
    "                move[s2[i]] = move.get(s2[i], 0)+1\n",
    "                if move[s2[i]] == record[s2[i]]:\n",
    "                    distance -= 1\n",
    "                    if distance==0:\n",
    "                        return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1) - 1, len(s2)\n",
    "        c1, c2 = Counter(s1), Counter(s2[: n1])\n",
    "        for i in range(n2 - n1):\n",
    "            c2[s2[i + n1]] += 1\n",
    "            if c1 == c2: return True\n",
    "            c2[s2[i]] -= 1 \n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        ref = {item: 0 for item in s2}\n",
    "        count = {item: 0 for item in s2}\n",
    "        for i in s1:\n",
    "            if i not in s2:\n",
    "                return False\n",
    "            else:\n",
    "                ref[i] += 1\n",
    "        n = len(s1)  # 长度为n的滑动窗口\n",
    "        for i in range(len(s2)):  # 按n长度滑动\n",
    "            if i < n:  # 前n个\n",
    "                count[s2[i]] += 1\n",
    "            else:\n",
    "                count[s2[i]] += 1\n",
    "                count[s2[i - n]] -= 1\n",
    "            if count == ref:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        def allZero(hash):\n",
    "            for i in range(len(hash)):\n",
    "                if hash[i] != 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "        hash = [0] * 26\n",
    "        #对应图中（a）（b），哈希表的初始化：s1中字符出现+1，s2中出现的字符-1\n",
    "        for i in range(len(s1)):\n",
    "            hash[ord(s1[i]) - ord('a')] += 1\n",
    "            hash[ord(s2[i]) - ord('a')] -= 1\n",
    "        if (allZero(hash) == True):\n",
    "            return True\n",
    "\n",
    "        # 对应图中（c）（d）\n",
    "        for i in range(len(s1),len(s2)):\n",
    "            #右指针\n",
    "            hash[ord(s2[i])-ord('a')] -= 1\n",
    "            #左指针\n",
    "            hash[ord(s2[i-len(s1)]) - ord('a')] += 1\n",
    "            \n",
    "            if (allZero(hash) == True):\n",
    "                return True\n",
    "\n",
    "        if (allZero(hash) == False):\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        arr1, arr2, lg = [0] * 26, [0] * 26, len(s1)\n",
    "        if lg > len(s2):\n",
    "            return False\n",
    "        for i in range(lg):\n",
    "            arr1[ord(s1[i]) - ord('a')] += 1\n",
    "            arr2[ord(s2[i]) - ord('a')] += 1\n",
    "        for j in range(lg, len(s2)):\n",
    "            if arr1 == arr2:\n",
    "                return True\n",
    "            arr2[ord(s2[j - lg]) - ord('a')] -= 1\n",
    "            arr2[ord(s2[j]) - ord('a')] += 1\n",
    "        return arr1 == arr2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/wo-xie-le--f02cd/\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    # 判断 s 中是否存在 t 的排列\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        windows = defaultdict(int)\n",
    "        left, right = 0, 0\n",
    "\n",
    "        need = defaultdict(int)\n",
    "        for i in s1:\n",
    "            need[i] += 1\n",
    "\n",
    "        valid = 0\n",
    "\n",
    "        while right < len(s2):\n",
    "            c = s2[right]\n",
    "            right += 1\n",
    "\n",
    "            if c in need:\n",
    "                windows[c] += 1\n",
    "                if windows[c] == need[c]:\n",
    "                    valid += 1\n",
    "           \n",
    "            while right - left == len(s1):\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "\n",
    "                d = s2[left]\n",
    "                left += 1\n",
    "                if d in need:\n",
    "                    if windows[d] == need[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "        return False\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        start = 0\n",
    "        template = Counter(s1)  \n",
    "        for end in range(len(s1) - 1, len(s2)):\n",
    "            if Counter(s2[start:end + 1]) == template:\n",
    "                return True\n",
    "            start += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        if len(s1)>len(s2): return False\n",
    "        map_1=[0]*26\n",
    "        map_2=[0]*26\n",
    "        l=0\n",
    "        r=0\n",
    "        while(r<len(s1)):\n",
    "            map_1[ord(s1[r])-ord('a')]+=1\n",
    "            map_2[ord(s2[r])-ord('a')]+=1\n",
    "            r+=1\n",
    "        if map_1==map_2: return True\n",
    "        while(r<len(s2)):\n",
    "            map_2[ord(s2[l])-ord('a')]-=1\n",
    "            map_2[ord(s2[r])-ord('a')]+=1\n",
    "            r+=1\n",
    "            l+=1\n",
    "            if map_1==map_2: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m > n:\n",
    "            return False\n",
    "        \n",
    "        s = Counter(s1)\n",
    "        t = Counter(s2[:m])\n",
    "        if s == t:\n",
    "            return True\n",
    "\n",
    "        for i in range(m, n):\n",
    "            t[s2[i - m]] -= 1\n",
    "            t[s2[i]] += 1\n",
    "            if t == s:\n",
    "                return True\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        l1, l2 = len(s1), len(s2)\n",
    "        if l1>l2:\n",
    "            return False\n",
    "        \n",
    "        d1, d2 = defaultdict(int), defaultdict(int)\n",
    "\n",
    "        for ch in s1:\n",
    "            d1[ch] += 1\n",
    "        \n",
    "        for ch in s2[:l1]:  # 先取s1长度的子串\n",
    "            d2[ch] += 1\n",
    "        if d1==d2:\n",
    "            return True\n",
    "        \n",
    "        for ch_idx in range(l1, l2):  # 右滑\n",
    "            left_ch = s2[ch_idx-l1]\n",
    "            d2[left_ch] -= 1\n",
    "            if d2[left_ch]==0:  # 左边字符数为0，则移除此键\n",
    "                del d2[left_ch]\n",
    "            cur_ch = s2[ch_idx]\n",
    "            d2[cur_ch] += 1\n",
    "            if d2==d1:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        # 统计s1中的字符出现次数\n",
    "        char2cnt = {}\n",
    "        for i in range(len(s1)):\n",
    "            char2cnt[s1[i]] = char2cnt.get(s1[i], 0) + 1\n",
    "        \n",
    "        left = 0\n",
    "        for right in range(len(s2)):\n",
    "            while left <= right and char2cnt.get(s2[right], 0) <= 0:\n",
    "                if s2[left] in char2cnt:\n",
    "                    char2cnt[s2[left]] += 1\n",
    "                left += 1\n",
    "\n",
    "            if char2cnt.get(s2[right], 0) > 0:\n",
    "                char2cnt[s2[right]] -= 1\n",
    "                \n",
    "            if right - left + 1 == len(s1) and sum(char2cnt.values()) == 0:\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import defaultdict\n",
    "        left,right = 0,0\n",
    "        d1,d2 = defaultdict(int),defaultdict(int)\n",
    "        for i in s1:\n",
    "            d1[i] += 1\n",
    "        valid = 0\n",
    "        while right < len(s2):\n",
    "            c = s2[right]\n",
    "            if c in d1:\n",
    "                d2[c] += 1\n",
    "                if d1[c] == d2[c]:\n",
    "                    valid += 1\n",
    "            right += 1\n",
    "            while valid == len(d1):\n",
    "                if right - left == len(s1):\n",
    "                    return True\n",
    "                d = s2[left]\n",
    "                if d in d1:\n",
    "                    d2[d] -= 1\n",
    "                    if d2[d] < d1[d]:\n",
    "                        valid -= 1\n",
    "                left += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter #返回哈希词频\n",
    "        target = Counter(s1)\n",
    "        window = Counter()\n",
    "        left, right = 0, 0\n",
    "        tmp = 0 \n",
    "        while right < len(s2):\n",
    "            char = s2[right]\n",
    "            right += 1\n",
    "            if char in target:\n",
    "                window[char] += 1\n",
    "                \n",
    "            if right - left == len(s1): \n",
    "                if window == target:\n",
    "                    return True\n",
    "                \n",
    "                char = s2[left]\n",
    "                if char in target:\n",
    "                   window[char] -= 1\n",
    "                left += 1\n",
    "\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        mapp = dict()\n",
    "        window = dict()\n",
    "        for s in s1:\n",
    "            if s in mapp.keys():\n",
    "                mapp[s] += 1\n",
    "            else:\n",
    "                mapp[s] = 1\n",
    "                window[s] = 0\n",
    "        \n",
    "        l, r = 0, 0\n",
    "        valid = 0\n",
    "        while r < len(s2):\n",
    "            c = s2[r]\n",
    "            r += 1\n",
    "            if mapp.get(c, 0):\n",
    "                window[c] += 1\n",
    "                if window[c] == mapp[c]:\n",
    "                    valid += 1\n",
    "\n",
    "            while r-l >= len(s1):\n",
    "                if valid == len(mapp):\n",
    "                    return True\n",
    "                d = s2[l]\n",
    "                l += 1\n",
    "                if mapp.get(d, 0):\n",
    "                    if window[d] == mapp[d]:\n",
    "                        valid -= 1\n",
    "                    window[d] -= 1\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m > n:\n",
    "            return False\n",
    "        base = {}\n",
    "        for ch in s1:\n",
    "            base[ch] = base.get(ch, 0) + 1\n",
    "        need = len(base)\n",
    "\n",
    "        mp = {ch: 0 for ch in base}\n",
    "        for i, ch in enumerate(s2):\n",
    "            if ch in mp:\n",
    "                mp[ch] += 1\n",
    "                if mp[ch] == base[ch]:\n",
    "                    need -= 1\n",
    "            if i-m >= 0:\n",
    "                ch = s2[i-m]\n",
    "                if ch in mp:\n",
    "                    if mp[ch] == base[ch]:\n",
    "                        need += 1\n",
    "                    mp[ch] -= 1\n",
    "            if need == 0:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        start = 0\n",
    "        template = Counter(s1)  \n",
    "        for end in range(len(s1) - 1, len(s2)):\n",
    "            if Counter(s2[start:end + 1]) == template:\n",
    "                return True\n",
    "            start += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m = len(s1)\n",
    "        n = len(s2)\n",
    "        \n",
    "        if m > n:\n",
    "            return False        \n",
    "        \n",
    "        cnt = collections.Counter(s1)    # 哈希表：记录需要匹配到的各个元素的数目\n",
    "        need = m                 # 记录需要匹配到的字符总数【need=0表示匹配到了】\n",
    "        \n",
    "        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾\n",
    "        \n",
    "        for end in range(n):\n",
    "            # 窗口右边界右移一位\n",
    "            if  need == 0:            # need=0，当前窗口完全覆盖了t\n",
    "                return True\n",
    "            ch = s2[end]               # 窗口中新加入的字符\n",
    "            if ch in cnt:               # 新加入的字符位于t中\n",
    "                if cnt[ch] > 0:         # 对当前字符ch还有需求\n",
    "                    need -= 1           # 此时新加入窗口中的ch对need有影响\n",
    "                cnt[ch] -= 1\n",
    "            if end-start+1>m:\n",
    "                ch = s2[start]\n",
    "                if ch in cnt:\n",
    "                    cnt[ch] += 1\n",
    "                    if cnt[ch] > 0:\n",
    "                        need += 1\n",
    "                start += 1\n",
    "            # print(start, end, need, cnt)\n",
    "        if need == 0:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        dc=Counter(s1)\n",
    "        n=len(s1)\n",
    "        p=Counter(s2[:n])\n",
    "        for i in range(n-1,len(s2)):\n",
    "            # print(p,n)\n",
    "            if i==n-1:\n",
    "                pass\n",
    "            else:\n",
    "                # print(s2[i],s2[i-n])\n",
    "                p[s2[i]]+=1\n",
    "                p[s2[i-n]]-=1\n",
    "                if p[s2[i-n]]==0:\n",
    "                    p.pop(s2[i-n])\n",
    "            flag=True\n",
    "            for j in dc:\n",
    "                if dc[j]!=p[j]:\n",
    "                    flag=False\n",
    "                    break\n",
    "            if flag:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        hs1 = {}\n",
    "        hs2 = {}\n",
    "        k = len(s1)\n",
    "        for i in s1:\n",
    "            if i in hs1:\n",
    "                hs1[i] += 1\n",
    "            else:\n",
    "                hs1[i] = 1\n",
    "            hs2[i] = 0\n",
    "    \n",
    "        left = 0\n",
    "        right = k-1\n",
    "        for i in s2[left:right+1]:\n",
    "            if i in hs2:\n",
    "                hs2[i] += 1\n",
    "            else:\n",
    "                hs2[i] = 1\n",
    "        for i in s2[right+1:]:\n",
    "            if i not in hs2:\n",
    "                hs2[i] = 0\n",
    "\n",
    "        print(hs1)\n",
    "        print(hs2)\n",
    "        while right < len(s2):\n",
    "            while right - left >= k:\n",
    "                hs2[s2[left]] -= 1\n",
    "                left += 1\n",
    "            \n",
    "            flag = True\n",
    "            for i in hs1.keys():\n",
    "                if hs1[i] != hs2[i]:\n",
    "                    flag = False\n",
    "                    break\n",
    "            if flag:\n",
    "                return True\n",
    "            right += 1\n",
    "            if right < len(s2):\n",
    "                hs2[s2[right]] += 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1) - 1, len(s2)\n",
    "        c1, c2 = Counter(s1), Counter(s2[: n1])\n",
    "        for i in range(n2 - n1):\n",
    "            c2[s2[i + n1]] += 1\n",
    "            if c1 == c2: return True\n",
    "            c2[s2[i]] -= 1 \n",
    "        return False\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        flag = False\n",
    "        for i in range(len(s2)):\n",
    "            if s2[i] in s1:\n",
    "                if i + len(s1) - 1 < len(s2):\n",
    "                    s = s2[i:i+len(s1)]\n",
    "                else:\n",
    "                    break\n",
    "                # print(s)\n",
    "                if sorted(s) == sorted(s1):\n",
    "                    flag = True\n",
    "                    break\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        start = 0\n",
    "        template = Counter(s1)  \n",
    "        for end in range(len(s1) - 1, len(s2)):\n",
    "            if Counter(s2[start:end + 1]) == template:\n",
    "                return True\n",
    "            start += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        def check(str1,str2):\n",
    "            if len(str2) != len(str1):\n",
    "                return False\n",
    "            for i in str1:\n",
    "                if i not in str2:\n",
    "                    return False\n",
    "            for i in str2:\n",
    "                if i not in str1:\n",
    "                    return False\n",
    "            count1 , count2= Counter(str1) , Counter(str2)\n",
    "            if count1.items() != count2.items():\n",
    "                return False\n",
    "            return True      \n",
    "        if len(s1) > len(s2):\n",
    "            return False\n",
    "        m , n = len(s1) , len(s2)\n",
    "        for i in range(n-m+1):\n",
    "            j = i + m\n",
    "            if check(s1,s2[i:j]):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import defaultdict\n",
    "        need = {}\n",
    "        windows = defaultdict(int)\n",
    "\n",
    "        for c in s1:\n",
    "            need.setdefault(c, 0)\n",
    "            need[c] += 1\n",
    "\n",
    "        \n",
    "        left, right, valid = 0, 0, 0\n",
    "\n",
    "        while right < len(s2):\n",
    "            c = s2[right]\n",
    "            right += 1\n",
    "            if need.get(c):\n",
    "                windows[c] += 1\n",
    "                if need[c] == windows[c]:\n",
    "                    valid += 1\n",
    "            \n",
    "            while right - left >= len(s1):\n",
    "                if valid == len(need):\n",
    "                    return True\n",
    "                d = s2[left]\n",
    "                left += 1\n",
    "                if need.get(d):\n",
    "                    if need[d] == windows[d]:\n",
    "                        valid -= 1\n",
    "                    windows[d] -= 1\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        from collections import Counter\n",
    "        start = 0\n",
    "        template = Counter(s1)  \n",
    "        for end in range(len(s1) - 1, len(s2)):\n",
    "            if Counter(s2[start:end + 1]) == template:\n",
    "                return True\n",
    "            start += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        \n",
    "        len_1, len_2 = len(s1), len(s2)\n",
    "        if len_1 > len_2: return False\n",
    "\n",
    "        map_s1 = Counter(s1)\n",
    "        for i in range(len_1): # 初始化窗口\n",
    "            if s2[i] in map_s1:\n",
    "                map_s1[s2[i]] -= 1\n",
    "            if max(list(map_s1.values())) == 0:\n",
    "                return True\n",
    "        \n",
    "        for p in range(len_1, len_2): # 滑窗\n",
    "            if s2[p] in map_s1:\n",
    "                map_s1[s2[p]] -= 1\n",
    "            if s2[p-len_1] in map_s1:\n",
    "                map_s1[s2[p-len_1]] += 1\n",
    "            if max(list(map_s1.values())) == 0:\n",
    "                print(map_s1)\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        if m > n: return False\n",
    "        need_count = m\n",
    "        need = collections.Counter(s1)\n",
    "\n",
    "        for right in range(n):\n",
    "            if s2[right] in need:\n",
    "                if need[s2[right]] > 0:\n",
    "                    need_count -= 1\n",
    "                need[s2[right]] -= 1\n",
    "            \n",
    "            left = right - m\n",
    "            if left >= 0:\n",
    "                if s2[left] in need:\n",
    "                    if need[s2[left]] >= 0:\n",
    "                        need_count += 1\n",
    "                    need[s2[left]] += 1\n",
    "            \n",
    "            if need_count == 0: return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # m, n = len(s1), len(s2)\n",
    "        # if m > n: return False\n",
    "        # need = collections.Counter(s1)\n",
    "        # need_count = m\n",
    "\n",
    "        # for right in range(n):\n",
    "        #     char = s2[right]\n",
    "        #     if char in need:\n",
    "        #         if need[char] > 0:\n",
    "        #             need_count -= 1\n",
    "        #         need[char] -= 1\n",
    "\n",
    "        #     left = right - m\n",
    "        #     if left >= 0:\n",
    "        #         char = s2[left]\n",
    "        #         if char in need:\n",
    "        #             if need[char] >= 0:\n",
    "        #                 need_count += 1\n",
    "        #             need[char] += 1\n",
    "            \n",
    "        #     if need_count == 0: return True\n",
    "        \n",
    "        # return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "\n",
    "        s1 = sorted(list(s1))\n",
    "        for i in range(n2-n1+1):\n",
    "            if sorted(list(s2[i:i+n1])) == s1:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        zerodict = [0]*26\n",
    "        n1 = len(s1)\n",
    "        s1dic = copy.copy(zerodict)\n",
    "        for i in s1:\n",
    "            s1dic[ord(i)-ord('a')] += 1 \n",
    "            \n",
    "        n2 = len(s2)\n",
    "        for i in range(n2-n1+1):\n",
    "            \n",
    "            if s2[i] in s1:\n",
    "                s1dic2 = copy.copy(s1dic)\n",
    "                flag = True\n",
    "                for j in range(i,i+n1):\n",
    "                    tmp = ord(s2[j])-ord('a')\n",
    "                    s1dic2[tmp] -= 1\n",
    "                    if s1dic2[tmp] == -1 :\n",
    "                        flag = False\n",
    "                        break\n",
    "                if flag:\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n = len(s1)\n",
    "        m = len(s2)\n",
    "        if n > m:\n",
    "            return False\n",
    "        cnt = [0] * 26\n",
    "        for i in range(n):\n",
    "            cnt[ord(s1[i]) - ord(\"a\")] -= 1\n",
    "            cnt[ord(s2[i]) - ord(\"a\")] += 1\n",
    "        diff = sum(c != 0 for c in cnt)\n",
    "        if diff == 0:\n",
    "            return True\n",
    "        for i in range(n, m):\n",
    "            x = ord(s2[i]) - ord(\"a\")\n",
    "            y = ord(s2[i-n]) - ord(\"a\")\n",
    "            if x == y:\n",
    "                continue\n",
    "            if cnt[x] == 0:\n",
    "                diff += 1\n",
    "            cnt[x] += 1\n",
    "            if cnt[x] == 0:\n",
    "                diff -= 1\n",
    "            if cnt[y] == 0:\n",
    "                diff += 1\n",
    "            cnt[y] -= 1\n",
    "            if cnt[y] == 0:\n",
    "                diff -= 1\n",
    "            if diff == 0:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m=len(s1)\n",
    "\n",
    "        target=dict()\n",
    "\n",
    "        for w in s1:\n",
    "            target[w]=target.get(w,0)+1\n",
    "            \n",
    "        n=len(s2)\n",
    "\n",
    "        if(m>n):\n",
    "            return False\n",
    "\n",
    "        cur=dict()\n",
    "\n",
    "        for i in range(m-1):\n",
    "            cur[s2[i]]=cur.get(s2[i],0)+1\n",
    "\n",
    "        for i in range(m-1,n):\n",
    "            cur[s2[i]]=cur.get(s2[i],0)+1\n",
    "            if(cur==target):\n",
    "                return True\n",
    "            cur[s2[i-m+1]]-=1\n",
    "            if not cur[s2[i-m+1]]:\n",
    "                del cur[s2[i-m+1]]\n",
    "                \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "        for i in range(n2-n1+1):\n",
    "            if sorted(s2[i:i + n1]) == sorted(s1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1, n2 = len(s1), len(s2)\n",
    "        if n1 > n2:\n",
    "            return False\n",
    "        cnt = [0] * 26\n",
    "        target = cnt.copy()\n",
    "        for s in s1:\n",
    "            target[ord(s) - 97] += 1\n",
    "        for i in range(n1):\n",
    "            cnt[ord(s2[i]) - 97] += 1\n",
    "        for i in range(n1, n2):\n",
    "            if cnt == target:\n",
    "                return True\n",
    "            cnt[ord(s2[i]) - 97] += 1\n",
    "            cnt[ord(s2[i - n1]) - 97] -= 1\n",
    "        return cnt == target\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  \n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        m, n = len(s1), len(s2)\n",
    "        counter = collections.Counter(s1)\n",
    "        need = m \n",
    "        #print(\"init\", counter)\n",
    "        for right in range(n):\n",
    "            ch = s2[right]\n",
    "            if ch in counter:\n",
    "                if counter[ch] > 0:          # NOTE 有需求\n",
    "                    need -= 1\n",
    "                counter[ch] -= 1\n",
    "            \n",
    "            left = right-m+1\n",
    "            if left-1>=0: \n",
    "                ch = s2[left-1]\n",
    "                if ch in counter:\n",
    "                    if counter[ch] >= 0:     # NOTE 勉强够 \n",
    "                        need += 1\n",
    "                    counter[ch] += 1\n",
    "            #print(left, right, s2[left: right+1], counter, need)# NOTE important, 积累 DEBUG 方式\n",
    "            if need == 0:\n",
    "                print(s2[left: right+1])\n",
    "                return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1,n2 = len(s1),len(s2)\n",
    "        if len(s1)>len(s2):\n",
    "            return False\n",
    "        for i in range(n2-n1+1):\n",
    "            num = s2[i:i+n1]\n",
    "            if sorted(s1) == sorted(num):\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkInclusion(self, s1: str, s2: str) -> bool:\n",
    "        n1 = len(s1)\n",
    "        n2 = len(s2)\n",
    "\n",
    "        s1 = sorted(list(s1))\n",
    "        print(s1)\n",
    "        for i in range(n2-n1+1):\n",
    "            if sorted(list(s2[i:i+n1])) == s1:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
